面试必知必会|堆和优先队列

通过本文将了解到以下内容：

• 优先队列的概念

• 优先队列的实现

• 优先队列的应用

---

1.优先队列的概念

优先队列是计算机科学中的一类抽象数据类型。

优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；

优先级相同的元素按照其在优先队列中的顺序得到服务。

优先队列至少需要支持下述操作：

a.插入带优先级的元素

b.取出具有最高优先级的元素

c.查看最高优先级的元素。

综合考虑插入和删除的性能 优先队列一般采用堆来实现。

维基百科-优先队列

---

由于优先队列的元素既可以是基础类型，也可以是复合类型，因此在C++中一般使用模板来定义优先队列，从而提高其可扩展性，简单定义：

template<class T>
class priqueue {
public:
       //构造函数 初始化
       priqueue(int maxsize);
       //将T类型新元素添加到队列中
       void insert(T t);
       //获取队列中最小的元素
       T extractmin();
};

---

2.优先队列的实现

实现优先队列的候选数据结构包括：有序序列、无序序列、堆。

• 有序序列

有序序列中存储的数据都是有序的，在执行extractmin获取最小值时复杂度O(1)，但是在添加新元素时就存在大量的移动和查找正确的位置最大复杂度O(N)，因此在insert和extactmin同时执行N次时，最大复杂度为O(N^2)。

• 无序序列

无序序列中存储的元素是无序的，在执行insert操作复杂度为O(1)，但是在extractmin时每次都要进行一次遍历复杂度为O(N)，因此在insert和extractmin同时执行N次时，最大复杂度为O(N^2)。

• 堆结构

从上一节我们知道堆的insert不如无序序列那么随意，extractmin也没有有序序列那么容易，每次都需要进行siftup和siftdn操作进行调整，但是同时执行insert和extractmin时，复杂度是O(nlogn)，优于O(N^2)。

• 复杂度对照
  

在数据量超过较大时O(N^2)的执行时间要比O(nlogn)大非常多，有兴趣可以试试，引用参考4中的数据曲线：

• 小结

综上可以知道，堆结构在实现优先队列的插入和删除操作时复杂性都很稳定，在大量数据的场景下优于有序序列和无序序列，因此权衡之下现在堆作为优先队列的底层数据结构。

3.优先队列的实现

• 基于模板化和堆的优先队列的简单实现

template<class T>
class priqueue {
    private:
        int n,maxsize;
        T *x;
        void swap(int i,int j)
        { T t = x[i]; x[i] = x[j]; x[j] = t; }
    public:
        //初始化
        priqueue(int m)
        { 
            maxsize = m;
            x = new T[maxsize+1];
            n = 0;
        }
        //插入新数据
        void insert(T t)
        { 
            int i,p;
            x[++n] = t;
            //末尾添加新数据 执行siftup操作
            for (i = n; i > 1 && x[p=i/2] > x[i]; i = p)
                swap(p,i);
        }
        //提取操作
        T extractmin()
       {
          int i,c;
          //提取堆顶元素
          T t = x[1];
          //将尾部元素放到堆顶
          x[1] = x[n--];
          //针对新堆顶进行siftdn操作
          for (i = 1; (c = 2*i) <= n; i = c) {
              if (c+1 <= n && x[c+1] < x[c])
                   c++;
              if (x[i] <= x[c])
                   break;
               swap(c,i);
          }
         return t;
      }
};

上述代码摘自编程珠玑并不是STL关于优先队列的实现，只是一部分简洁的代码，旨在表现insert和extract操作时如何运用堆的siftup和siftdn操作来封装成优先队列类的基础成员函数。

• 优先队列的自定义优先级

模板化的优先队列扩展了使用场景，但是也产生了新的问题，就是默认的优先级比较函数不一定满足所有要求，因此很多时候都需要自己来定义优先级判定函数。

实现了一个模板优先队列需要三个参数：

• 容器元素的类型
  

• 存储数据所用的容器

• 比较函数 缺省情况是less<T>

#include<quque>
// 队列和优先队列的声明
std::queue<T> pq;
std::priority_queue<T, std::vector<T>, cmp> pq;
//模板化优先队列的主要参数
priority_queue<Type, Container, Func>
//举例
priority_queue<pair<char,int>,vector<pair<char,int>>,compare> pq;
//自定义比较函数
struct compare
{
    bool operator()(const pair<char,int> a,const pair<char,int> b){
        return b.second > a.second;
    }  
};

4.优先队列的应用

上面的介绍可以认为优先队列是对堆的工具化封装，加上模板和自定义比较函数两个利器加持，优先队列让使用者不再苦于堆排序的原始造轮子。

• TopN问题

仍然以LeetCode 215题为例，获取数组的第K大元素，上一节中我们直接使用堆，但是构建的是小顶堆，并且大小是K个元素，遍历完成之后直接取堆顶即可，但是在数据量不大或者内存足够的情况下，可以直接建立优先队列。

默认的优先队列本质上是大顶堆，那么堆顶就不是第K大元素了，但是从堆顶开始依次pop出K-1个元素，堆顶也就是第K大元素了。

当然也可以修改比较函数实现小顶堆，取堆顶元素也是可以的，要灵活运用。

使用优先队列实现LeetCode 第215题，代码如下：

//默认的比较函数是less 也就是优先队列相当于最大堆
//堆顶元素为最大值
priority_queue<int,vector<int>,less<int>> q;

int findKthLargest(vector<int>& nums, int k) 
{
  priority_queue<int> q(nums.begin(),nums.end());
  for(int i=0;i<k-1;i++) 
      q.pop();
  return q.top();
}

• 优先队列和贪心算法

贪心算法又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法。 

贪心算法在有最优子结构的问题中尤为有效。

最优子结构的意思是局部最优解能决定全局最优解。

简单地说问题能够分解成子问题来解决，子问题的最优解递推到最终问题的最优解。

维基百科-贪心算法

优先队列是贪心算法的重要组成部分，借助于优先队列贪心算法可以解决非常多的实际问题其中包括：

• 旅行商TSP问题

• 01背包问题

• 霍夫曼编码问题

• 最短路径Dijkstra算法

• 最小生成树Prim算法

---

5.参考资料

• 《编程珠玑》

• http://www.laicar.com/book/echapter/5cb0a77e739207662ac8710c/links/item10/OEBPS/Text/part0009.xhtml

• 维基百科

• https://my.oschina.net/u/1246663/blog/227115

---

6.往期精彩